Interactive computer graphics applications frequently require that two-dimensional labels be attached to objects that are displayed on a screen. Such labels provide information about the objects they are related to and are useful for users of such systems. These labels are typically drawn as a two-dimensional overlay on top of the two-dimensional or three-dimensional graphical object rendition that otherwise appears on the graphics display screen. One example of such an application is an air traffic control system where a graphical display of aircraft in flight is rendered on a display screen for use by an air traffic controller in controlling air traffic within a given region of interest. Within the region, for each real aircraft, there is rendered a displayed aircraft icon. Each aircraft icon has a two-dimensional label is attached to it, providing crucial information such as flight number, speed and altitude.
Since the airplanes move in and out of the region of interest over time, so do the aircraft icons and their respective labels. Because the air traffic controllers need ready access to all the information presented on their computer graphical display, it is important to prevent the labels from overlapping each other and other crucial features in the display such as the aircraft themselves. This can cause the information presented to become very difficult to read. In certain circumstances, overlap problems become so severe that the controllers cannot read the labels or other features on the display.
In some air traffic control computer graphical displays, the users must manually reposition the labels so that they do not overlap or hide other useful information. This step requires additional work on the user's part and is, in fact, not even a practical solution in the case of a three-dimensional perspective graphical display, where changing the viewpoint causes large changes in the spatial relationship of the displayed graphical objects.
The problem of how to reposition labels to alleviate the forgoing problems may appear intuitively simple at first, but it is actually quite difficult. The general problem is known to be ‘NP-hard’ by those of skill in the art. That means that for large problems it is not possible (within the current understanding of computer systems) to generate a system that can find the optimal solution to the problem in a reasonable amount of time. This is because finding the optimal solution requires searching through the entire potential search space. Previous automated label placement schemes do exist, however, all have limitations that result in them being less effective than is needed and desired.
In addition to the air traffic control systems, object label placement on computer graphical displays can be problematic in other applications as well. For example, similar labeling problems occur in command and control displays, which show the location of friendly and enemy units on two-dimensional or three-dimensional displays. Automatic label placement may also eventually be needed in ‘Augmented Reality’ displays (which display virtual labels over three-dimensional real objects in the environment as a person looks around). Aircraft head-up displays are another example of where object label placement may becomes increasingly important.
The object label placement problem for computer graphics applications is closely related to placement problems for static displays, such as maps. Cartographers have long faced the problem of assigning text labels to map features while avoiding label overlap and covering other important features. There are a number of references, but a good summary and evaluation of existing techniques is provided in: “An Empirical Study of Algorithms for Point-Feature Label Placement”, published by Jon Christensen, Joe Marks, and Stuart Shieber in ACM Transactions on Graphics 14, 3 (July 1995). An extended version by the same author is provided in Labeling Point Features on Maps and Diagrams. Technical Report TR-25-92. Center for Computer Technology, Harvard University, 1992 (revised June 1994). Another version of this discussion is available in Graphics Gems IV, Paul Heckbert (editor), Cambridge Academic Press, 1994.
In fact, label placement problems have proven to be NP-hard. For example, in a situation where each aircraft label can be placed in one of twenty positions adjacent to the aircraft, and where there are one-hundred total aircraft in the region of interest and on the graphical display screen, the search space consists of 20100 total sets of possible positions to evaluate. Clearly, this is far too many to evaluate in any reasonable time frame given the current state of computational technologies. Thus, an NP-hard problem means that there is no way to sufficiently prune this search space to avoid exponential growth caused by the combinatorics of the problem. A conceptual way of thinking about this is to imagine placing one label down on one aircraft. That takes up space that is no longer available for any other label. It is possible that, as labels continue to be placed, the situation will eventually arise where another aircraft label requires the space occupied by the first aircraft's label. Thus, decisions made early on in the label placement process can have ramifications much later in the placement process. The problem grows exponentially as the number of aircraft and possible label positions increase.
Existing label placement algorithms can be divided into two categories: exhaustive search and greedy search. Exhaustive search techniques essentially perform Depth First Searching with various bracketing and pruning heuristics. They are effective only on a small data set and are known to be less practical than greedy search algorithms. Greedy algorithms do not guarantee an optimal solution, however, finish in a practical amount of time by limiting the search space. A wide variety of greedy algorithms exist, ranging from random placement, to force-based methods, to mathematic optimization techniques, and discrete gradient descent (i.e. repositioning one or more randomly-chosen labels simultaneously and keeping the new configuration if it results in an overall improvement). Greedy algorithms in general have trouble escaping from local minima. Local minima are effectively non-optimal solutions that require repositioning large numbers of labels simultaneously to overcome the dangers associated with the solution. One particular algorithm is called ‘Simulated Annealing’ yields the best results. It is essentially a stochastic gradient descent search that sometimes allows the label placement to change to a worse solution, according to a particular schedule. ‘Simulated Annealing’ has the characteristic that as the time it is allowed to run approaches infinity, the solution generated approaches the optimum. The references above compare all published algorithms and conclude that Simulated Annealing finds a better solution than all other algorithms for all sizes of data sets.
The problem domain for label placement in an interactive computer graphics environment differs significantly from label placement for static maps and displays. In an interactive computer graphics environment, the three main differences are that; (1) the labeled objects change position with time, (2) little time is available for computing the label positions (a fraction of a second), and, (3) a human user observes the labels as they move around the display. Therefore, the object label placement system should minimize performing actions that distract the user from the underlying tasks. In the case of a static map, a placement system can run for several minutes, or longer, to generate a good solution. In an interactive computer graphics application, the time allotted for such calculations may have to be limited to 100 milliseconds, or less per iteration. Thus, the problem becomes finding a ‘good enough’ solution within the available time. Simulated annealing is not an appropriate solution for the interactive computer graphics application. The computation time required is too large to support in an interactive application, and it does not give any consideration to the cognitive distraction potentially caused by the solution.
Heuristic methods for interactive computer graphics applications focus on generating solutions with minimal computation and limited exploration of the total search space. Two main types of solutions have been tried, and they are force-based methods and fixed-position methods.
Force-based methods are commonly used in visualization of graphs and other objects. Labels and objects that are not to be covered are given a repulsion force. Other labels that encroach on such an object are ‘pushed away’ by a repulsion force inversely proportional to the separation distance. These forces are often modeled on springs or gravitational forces. In practice, force-based methods perform poorly respecting the label placement problem. They are vulnerable to getting stuck in local minima, even in simple cases. For example, when two aircraft cross paths, their associated labels can get stuck on the opposite sides because the repulsive forces prevent them from crossing paths. The optimum solution is for the two labels to swap positions, but the force-based technique instead pushes the labels in the opposite directions. Force-based schemes also perform poorly in the area of minimizing cognitive distractions. Labels stuck in between other labels or objects are jostled about; resulting in oscillations and wiggling that attract unwarranted user attention.
Another approach is the examination of a fixed number of label positions about an object. In general, this is a locally greedy approach with no backtracking. Each aircraft has a fixed number of positions where the labels can be placed in positions spaced equally about and relative to the aircraft icon. For example, there may be eight positions equally spaced about a circle with the aircraft icon located at the center of the circle. The system then iterates through all the aircraft icons on the display, one by one, in some order. For each aircraft, it checks all eight spaces to see which are empty, and puts the label in an empty position (if available, in the preferred location, such as the upper right corner). If none are empty, it picks one of the positions that causes the least amount of overlap. This method is efficient because of its simplicity and can generate reasonable results. However, it is very susceptible to local minima, and in practice the labels placed according to these solutions tend to oscillate.
Thus there is a need in the art for a method and apparatus for placing two-dimensional labels on an interactive computer graphics display.